The innermost computational kernel of many large numerical problems is often a large sparse matrix problem, which typically consumes a significant portion of the overall computational time required by the problem. Applications in numerous fields make intensive use of matrix computations, including Aerospace and automotive industries, computational fluid dynamics (CFD), defense, digital content creation, digital media, electronics, energy, finance, economic and financial forecasting, computational chemistry, molecular biology, computational physics, civil engineering, environmental engineering, gaming, geophysics, image processing, information processing services, life sciences, media, medicine, semiconductors, telecommunications, weather and climate research, weather forecasting, etc.
The methods for solving linear systems of equations are usually divided into direct and iterative. Also, depending on the structure of the problem, they can be divided into the ones that solve dense problems and the ones that solve sparse problems. It is not clear the best way to solve a large linear system of equations. However there are some indications that the selection of the kind of method depends very much on the particular problem: the sparsity and nonzero structure of the matrix, the efficiency of the preconditioner for the iterative method, and even a bit on the right hand side. In general, it is accepted to use direct methods for 1D and 2D problems, and iterative methods for 3D problems.
Direct methods are general techniques that provide high accuracy because they are analytical solutions. They usually have high memory costs and are advantageous when different right hand vectors are present. Examples of direct methods are: matrix inverse, Gaussian elimination, LU decomposition, QR decomposition, and Cholesky factorizaton
Iterative methods generate a sequence of iterates that are approximate solutions, and hopefully converge quickly towards the exact solution. Iterative methods efficiency depends on the type of the problem and the preconditioner used. If the preconditioner provides a matrix with a good condition number then the solution can be faster than the direct solution. The preconditioner is a transformation matrix that is used to convert the coefficient matrix into one with a more favorable spectrum (related with an improvement of the condition number). Iterative methods generally have lower memory costs but changing the right-hand vector implies solving the whole problem again. Iterative methods can be divided into stationary and non stationary methods. Non stationary methods differ from stationary methods in that the computations involve information that changes at each iteration. Examples of stationary methods are the Jacobi's method, Gauss-Seidel, Successive Overrelaxation (SOR), and Symmetric SOR. Examples of non stationary methods include Conjugate Gradient, Minimum Residual, and Generalized Minimum Residual.
In general, the problem of solving these systems of equations is addressed by software solutions, which translates into the use of traditional processor-based von Neumann architectures. For direct methods, that are the methods that can guarantee exact solutions, current solutions are still slow for a large number of applications, where, given the size of the problem, can take from hours to months to be solved.
There is then a need for a system and method for faster solutions of matrix problems, able to guarantee the delivery of accurate results. It is desired that this new systems and method could be easily integrated into a large number of engineering and science applications.